Giải thuật đầu tiên để tìm cây bao trùm nhỏ nhất do nhà khoa học người Séc Otakar Borůvka nghĩ ra vào năm 1926 (xem Giải thuật của Borůvka). Mục đích của ông là nghĩ ra cách phủ mạng điện hiệu quả tại Moravia. Hiện nay có hai giải thuật thường được sử dụng: Giải thuật của Prim và Giải thuật của Kruskal. Cả ba giải thuật này đều thuộc dạng giải thuật tham lam chạy với thời gian đa thức, vì vậy bài toán tìm cây bao trùm nhỏ nhất là dạng FP, và các bài toán ra quyết định liên quan như xác định xem một cạnh cụ thể có thuộc MST hay không hoặc xác định xem tổng trọng số tối thiểu có vượt quá một giá trị nào đó hay không, là thuộc dạng P. Một giải thuật tham lam khác không được phổ biến bằng đó là giải thuật ngược-xóa, là dạng đảo ngược của giải thuật của Kruskal.

Nếu trọng số của cạnh là số nguyên, thì giải thuật các đơn định giải được bài toán với O(m + n) phép tính nguyên.[1] Một mô hình khác, trong đó chỉ cho phép các phép tính trên trọng số của cạnh là so sánh đôi một, Karger, Klein & Tarjan (1995) đã tìm ra một giải thuật ngẫu nhiên hóa có thời gian tuyến tính dựa trên sự phối hợp giải thuật Borůvka và giải thuật ngược-xóa.[2][3] Tuy vậy, việc bài toán có thể được giải một cách đơn định trong thời gian tuyến tính bằng một giải thuật so sánh hay không vẫn còn là một câu hỏi mở. Giải thuật so sánh không ngẫu nhiên nhanh nhất, do Bernard Chazelle nghĩ ra, dựa trên đống mềm (soft heap),một dạng hàng đợi có ưu tiên xấp xỉ.[4][5]Thời gian chạy của nó là O(m α(m,n)), trong đó m là số cạnh, n là số đỉnh và α là hàm đảo cổ điển của Hàm số Ackermann. Hàm α tăng cực chậm, vì vậy khi áp dụng vào thực tế người ta thường cho nó là một hằng số không lớn hơn 4; vì thế giải thuật của Chazelle đạt rất gần đến thời gian tuyến tính. Seth Pettie và Vijaya Ramachandran đã tìm thấy giải thuật tìm cây bao trùm nhỏ nhất dựa trên phép so sánh đơn định có thể chứng minh được là tối ưu, tuy vậy độ phức tạp tính toán của nó hiện vẫn chưa biết.[6]

Những nhà nghiên cứu cũng xem xét các giải thuật song song cho bài toán cây bao trùm nhỏ nhất.Với một số bộ xử lý tuyến tính, ta có thể giải bài toán trong thời gian O ( log ⁡ n ) {\displaystyle O(\log n)} .[7][8]Bader & Cong (2003) mô tả một giải thuật có thể tính MST trên 8 bộ xử lý nhanh gấp 5 lần so với giải thuật tuần tự đã tối ưu hóa.[9] Thông thường, giải thuật tuần tự được dựa trên giải thuật Borůvka—Prim và đặc biệt, giải thuật của Kruskal không tốt hơn được như vậy khi có thêm bộ xử lý.

Các giải thuật chuyên biệt khác đã được thiết kế để tính cây bao trùm nhỏ nhất của một đồ thị lớn đến phải luôn lưu trữ nó trong đĩa. Các giải thuật bộ lưu trữ gắn ngoài này, như một ví dụ mô tả trong "Engineering an External Memory Minimum Spanning Tree Algorithm" của Roman Dementiev và đồng nghiệp,[10] có thể chạy chỉ chậm hơn có 2 đến 5 lần so với giải thuật với bộ nhớ cổ điển; họ cho rằng "các bài toán cây bao trùm nhỏ nhất cực kỳ lớn chứa trong vài đĩa cứng có thể được giải trên một máy PC chỉ trong một đêm". Họ dựa trên giải thuật sắp xếp hiệu quả trên bộ lưu trữ gắn ngoài và các kỹ thuật thu nhỏ đồ thị để giảm kích thước đồ thị một cách hiệu quả.

Bài toán này còn được tiếp cận theo cách phân bố. Nếu mỗi nút được xem là một máy tính và các nút không biết gì hết ngoài các liên kết mà nó liên kết, người ta vẫn có thể tính được cây bao trùm tối tiểu phân bố.